package algorithm;

/**
 * @author dushougudu
 */
public class Sudoku {

    public static int x = 3;
    public static int y = 3;
    public static int area = x * y;

    public static void main(String[] args) {
        char[][] nums = {
                {'.', '5', '.', '.', '8', '.', '6', '.', '.'},
                {'4', '.', '.', '9', '6', '2', '.', '.', '7'},
                {'.', '.', '8', '.', '1', '.', '.', '3', '.'},
                {'.', '.', '.', '.', '.', '.', '9', '5', '.'},
                {'.', '.', '.', '.', '4', '.', '1', '.', '3'},
                {'.', '.', '.', '6', '.', '3', '.', '.', '.'},
                {'.', '.', '.', '7', '.', '4', '.', '.', '.'},
                {'5', '.', '4', '.', '2', '.', '.', '.', '.'},
                {'.', '9', '1', '.', '.', '.', '.', '.', '.'},
        };

        dfs(nums, 0);
    }


    public static void dfs(char[][] nums, int pos) {
        if (pos >= area * area) {
            for (int i = 0; i < nums.length; i++) {
                for (int j = 0; j < nums[i].length; j++) {
                    System.out.print(nums[i][j]);
                }
                System.out.println();
            }
            return;
        }
        int row = pos / area;
        int column = pos % area;

        pos++;

        if (nums[row][column] != '.') {
            dfs(nums, pos);
            return;
        }

        for (int i = 1; i <= area; i++) {
            if (check(nums, (char) (i + '0'), row, column)) {
                char temp = nums[row][column];
                nums[row][column] = (char) (i + '0');
                dfs(nums, pos);
                nums[row][column] = temp;
            }
        }

    }

    public static boolean check(char[][] nums, char data, int row, int column) {

        for (int i = 0; i < nums.length; i++) {
            if (data == nums[i][column]) {
                return false;
            }
        }

        for (int i = 0; i < nums[row].length; i++) {
            if (data == nums[row][i]) {
                return false;
            }
        }

        int blockRow = row / y * y;
        int blockColumn = column / x * x;

        for (int i = blockRow; i < blockRow + y; i++) {
            for (int j = blockColumn; j < blockColumn + x; j++) {
                if (data == nums[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }

}
